package com.ljc;

import com.ljc.dto.TreeNode;
import org.omg.CORBA.INTF_REPOS;

import java.util.ArrayList;
import java.util.List;

/**
 * @author clj
 * @date 2022/12/2
 * @desc
 * Given the roots of two binary trees p and q, write a function to check if they are the same or not.
 * Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
 *
 * Example 1:
 * Input: p = [1,2,3], q = [1,2,3]
 * Output: true
 *
 *  Example 2:
 * Input: p = [1,2], q = [1,null,2]
 * Output: false
 *
 *  Example 3:
 * Input: p = [1,2,1], q = [1,1,2]
 * Output: false
 */
public class E100SameTree {
    public static void main(String[] args) {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);

        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(4);

        System.out.println(checkSameTree(p, q));

        System.out.println(isSameTree(p, q));

    }


    /**
     * 递归判断
     * 先检查根节点是否相同，若不相同，则直接返回false，否则，继续判断左子树和右子树是否相同
     * 方法一：深度优先搜索
     * 如果两个二叉树都为空，则两个二叉树相同。如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
     *
     * 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，
     * 若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
     * 这是一个递归的过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。
     *
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }


    public static boolean checkSameTree(TreeNode p, TreeNode q) {
        List<Integer> pres = inorderTraversal(p);
        List<Integer> qres = inorderTraversal(q);

        if (p == null && q == null ) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else {
            return pres.equals(qres);
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public static void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }

        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }


}
